package interview.removeduplicate;

import java.util.ArrayList;

public class RemoveDuplicate {
	public ArrayList<Integer> execute(Node head) {
		ArrayList<Integer> result = new ArrayList<Integer>();
		
		Node current = head.getNext();
		head.setNext(null);
		while(current != null) {
			Node runner = head;
			Node prev = null;
			while(runner != null && current.getData() > runner.getData()) {
				prev = runner;
				runner = runner.getNext();
			}
			
			Node tmp = current;
			current = current.getNext();
			
			if(prev == null && head.getData() != tmp.getData()) {
				tmp.setNext(head);
				head = tmp;
			} else if(runner == null) {
				prev.setNext(tmp);
				tmp.setNext(null);
			} else if(runner.getData() != tmp.getData()) {
				tmp.setNext(runner);
				prev.setNext(tmp);
			}
		}
		
		while(head != null) {
			result.add(head.getData());
			head = head.getNext();
		}
		
		return result;
	}
}
